package lc_面试题_17_06_2出现的次数;

import java.util.Arrays;

public class Solution2 {
	Integer[][] dp;
	char[] array;

	public int numberOf2sInRange(int n) {
		array = String.valueOf(n).toCharArray();
		dp = new Integer[array.length][10];
		return f(0, 1, 0);
	}

	private int f(int index, int ceil, int cnt) {
		if (index == array.length) {
			return cnt;
		}
		if (ceil == 0 && dp[index][cnt] != null) {
			return dp[index][cnt];
		}
		int up = ceil == 1 ? array[index] - '0' : 9;
		int ans = 0;
		for (int i = 0; i <= up; i++) {
			ans += f(index + 1, ceil == 1 && i == up ? 1 : 0, cnt + (i == 2 ? 1 : 0));
		}
		if (ceil == 0)
			dp[index][cnt] = ans;
		return ans;
	}

	class Solution {
		char arr[];
		int dp[][];

		public int numberOf2sInRange(int n) {
			arr = Integer.toString(n).toCharArray();
			int m = arr.length;
			dp = new int[m][10];
			for (int inn[] : dp) {
				Arrays.fill(inn, -1);
			}
			return f(0, 0, true);
		}

		public int f(int i, int n, boolean is) {
			if (i == arr.length)
				return n;
			if (!is && dp[i][n] != -1)
				return dp[i][n];
			int max = is ? arr[i] - '0' : 9;
			int ans = 0;
			for (int j = 0; j <= max; j++) {
				ans += f(i + 1, n + (j == 2 ? 1 : 0), is && j == max);
			}
			if (!is)
				dp[i][n] = ans;
			return ans;
		}
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		System.out.println(so.numberOf2sInRange(25));
	}
}